import Node from '../types/INode'

import {btPrint} from 'hy-algokit'

class TreeNode<T> extends Node<T> {
    left : TreeNode<T> | null = null;
    right : TreeNode<T> | null = null;

    parent : TreeNode<T> | null = null;
    // 加get的时候  用这个isLeft的时候不用加括号
    get isLeft():boolean{
        // 当前节点父节点的左子节点等于自身，则当前节点的就是其的左子节点
        return !!(this.parent && this.parent.left ===this)
    }

    get isRight():boolean{
        // 当前节点父节点的左子节点等于自身，则当前节点的就是其的左子节点
        return !!(this.parent && this.parent.right ===this)
    }
}

class BSTree<T> {
    private root: TreeNode<T> | null = null;

    private searchNode(value: T): TreeNode<T> | null {
        let current = this.root;
        let parent: TreeNode<T> | null = null;
        while(current){
             // 1、如果找到current 直接返回即可
            if (current.value === value) return current

            // 2、继续向下找
            parent = current;
            if (current.value < value) {
                current = current.right
            } else {
            current = current.left
          }
           // 如果current有值，那么current保存自己的父节点
         if (current) current.parent = parent
        }
        return null;
    }

    print(){
        btPrint(this.root)
    }

    // 插入数据的操作
    insert(value:T){
        // 1、根据传入value创建Node(TreeNode)节点
        const newNode = new TreeNode<T>(value)

        // 2、判断当前是否有根节点
        if(!this.root){//当前树为空
            this.root = newNode;
        }else{// 树中已经有其他值
            this.insertNode(this.root,newNode)
        }
    }
    private insertNode(node: TreeNode<T>,newNode: TreeNode<T>){
        if(newNode.value < node.value){// 去左边继续查找空白位置
            if(node.left === null){// node节点的左边已经是空白
                node.left = newNode
            }else{
                this.insertNode(node.left,newNode)
            }
        }else{
            if(node.right === null){
                node.right = newNode
            }else{
                this.insertNode(node.right,newNode)
            }
        }
    }

    // 遍历的操作
    // 先序遍历
    preOrderTraverse(){
        this.preOrderTraverseNode(this.root)
    }
   private preOrderTraverseNode(node:TreeNode<T> | null){
        if(node){
            console.log(node.value)
            this.preOrderTraverseNode(node.left)
            this.preOrderTraverseNode(node.right)
        }
    }

    // 中序遍历
    inOrderTraverse(){
        this.inOrderTraverseNode(this.root)
    }
    private inOrderTraverseNode(node:TreeNode<T> | null){
        if(node){
            this.inOrderTraverseNode(node.left)
            console.log(node.value)
            this.inOrderTraverseNode(node.right)
        }
    }

    // 后序遍历
    postOrderTraverse(){
        this.postOrderTraverseNode(this.root)
    }
   private postOrderTraverseNode(node:TreeNode<T> | null){
        if(node){
            this.postOrderTraverseNode(node.left)
            this.postOrderTraverseNode(node.right)
            console.log(node.value)
        }
    }

    // 层序遍历(使用队列)
    levelOrderTraverse(){
        // 1、如果没有根节点，不需要遍历
        if(!this.root) return;
        // 2、创建队列
        const queue: TreeNode<T>[] = [];
        // 第一个节点是根节点
        queue.push(this.root);
        while(queue.length){
            // 3.1访问节点的过程,这里肯定是有数据的,素偶哦加个断言
            const current = queue.shift()!
            console.log(current.value)

            // 3.2 将左子节点放入到队列里面
            if(current.left){
                queue.push(current.left);
            }
            // 3.2 将右子节点放入到队列里面
            if(current.right){
                queue.push(current.right);
            }
        }
    }

    // 获取最值操作(最大值和最小值)
    getMaxValue(): T | null {
        let current = this.root;
        while(current && current.right){
            current = current.right;
        }
        return current?.value ?? null;
    }

    getMinValue(): T | null {
        let current = this.root;
        while(current && current.left){
            current = current.left;
        }
        return current?.value ?? null;
    }

    // 实现删除操作(在要删除的节点中的右子树中找出后继节点)
    private getSuccessor(delNode:TreeNode<T>): TreeNode<T>{
        // 获取右子树
        let current = delNode.right;
        let successor: TreeNode<T> | null = null;
        while(current){
            successor = current;
            current = current.left;
            if(current){
                // 这里是让 successor一直有值,这样第172行的successor的父节点一定有值
                current.parent = successor;
            }
        }

        // 拿到了后继节点,当后继节点不是要删除节点的右子节点时，要将要删除节点的右子节点整体的放在后继节点的右侧
        if(delNode.right != successor){
            // 后继节点不是叶子节点，但是后继节点要被提上去了，所以它的右节点(这里不会是左节点(不然后继节点将会是其的左节点))要被放在其父节点的子左侧
            successor!.parent!.left = successor!.right ?? null
            successor!.right =  delNode.right;
        }



        // 找到后继节点
        console.log('删除节点',delNode.value,'后继节点',successor?.value)

        // 一定要进行的操作,将删除节点的left ,赋值给后继节点的left
        successor!.left = delNode.left
        return successor!
    }

    // 搜索特定的值：20 => boolean
    search(value:T):boolean {
        return !!this.searchNode(value)
    }

    remove(value:T):boolean {
        // 1、搜索当前是否有value
        let current = this.searchNode(value)
        if(!current) return false

        // 2、获取到3个东西: 当前节点/父节点/是属于父节点的左子节点还是右子节点
        // console.log('当前节点',current?.value,"父节点:",current?.parent?.value)
         // 2、如果删除的是叶子节点
        if(current.left === null && current.right === null){ 
            if(current === this.root){// 根节点
                this.root = null;
            }else if(current.isLeft){ // 父节点的左子节点
                current.parent!.left = null;
            }else{ // 父节点的右子节点
                current.parent!.right = null;
            }
        }
         // 3、只有一个子节点: 只有左子节点
         else if(current.right === null){
            if(current === this.root){ // 要删除的节点是根节点
                this.root = current.left;
            }else if(current.isLeft){  // 要删除的节点是在其父节点的左侧
                current.parent!.left = current.left;
            }else {  // 要删除的节点是在其父节点的右侧
                current.parent!.right = current.left;
            }
         }
        // 4、只有一个子节点: 只有右子节点
         else if(current.left === null){
            if(current === this.root){
                this.root = current.right;
            }else if(current.isLeft){
                current.parent!.left = current.right;
            }else {
                current.parent!.right = current.right;
            }
         }
         
         // 5、 有两个子节点
         else{
            const successor = this.getSuccessor(current)
            if(current === this.root){
                this.root = successor;
            }else if(current.isLeft){
                current.parent!.left = successor
            }else{
                current.parent!.right = successor
            }
         }

        return true
    }
}

 const bst = new BSTree<number>()
 bst.insert(11)
 bst.insert(7)

 bst.insert(15)

 bst.insert(5)
 bst.insert(3)
 bst.insert(9)
 bst.insert(8)
 bst.insert(10)
 bst.insert(13)
 bst.insert(12)
 bst.insert(14)
 bst.insert(20)
 bst.insert(18)
 bst.insert(25)
 bst.insert(6)

bst.print()

// 删除功能, 删除有两个节点的情况
bst.remove(11)
bst.print()
bst.remove(15)
bst.remove(9)
bst.print()
bst.remove(7)
bst.print()


export default {}